package com.freedy.dataStructure.sort;

import java.util.Arrays;

/**
 * @author Freedy
 * @date 2021/3/19 22:39
 */
public class QuickSort {
    public static void main(String[] args) {
        //20个随机数
        int[] arr = {368, 93, 284, 507, 204, 620, 331, 573, 910, 977,
                711, 305, 825, 438, 698, 49, 868, 241, 598, 737};
        sort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }

    public static void sort(int[] arr, int l, int r) {
        int left = l;
        int right = r;
        //中轴值
        int pivot = arr[(left + right) / 2];
        int temp = 0;
        while (left < right) {
            //寻找适合的值进行交换
            while (arr[left] < pivot) left++;
            while (arr[right] > pivot) right--;
            //当满足条件提前退出，不然可能发生数组越界
            if (right <= left) break;
            //交换两个元素
            temp = arr[left];
            arr[left] = arr[right];
            arr[right] = temp;
            //防止arr[left]==pivot==arr[right]时发生死循环
            if (arr[left] == pivot) right--;
            if (arr[right] == pivot) left++;
        }
        //防止发生死循环,例如当l=0，r=1且arr[l]>arr[r]时,经过上面的交换后会得到left=right=1
        //如果不错开则会调用sort(arr, 0, 1),这时就又回到上面那种情况了,所以会发生死循环
        if (left == right) {
            left++;
            right--;
        }

        if (l < right) sort(arr, l, right);
        if (left < r ) sort(arr, left, r);
    }

}
